/*
 * test/test-all.cc - All-in-one test unit.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

#include HEADER (LIBBST_PREFIX,node.hh)
#include HEADER (LIBBST_PREFIX,parent_node.hh)
#include HEADER (LIBBST_PREFIX,thread_node.hh)

#include HEADER (LIBBST_PREFIX,tree.hh)
#include HEADER (LIBBST_PREFIX,avl_tree.hh)
#include HEADER (LIBBST_PREFIX,rb_tree.hh)
#include HEADER (LIBBST_PREFIX,splay_tree.hh)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace LIBBST_NS;

struct container_t
{
  union
    {
      basic_node_t node;
      basic_parent_pn_node_t parent_node;
      basic_thread_node_t thread_node;
    };
  int value;
  bool in_tree_p;

  INLINE
  bool
  operator== (const container_t &c) const
  {
    return value == c.value;
  }

  INLINE
  bool
  operator< (const container_t &c) const
  {
    return value < c.value;
  }

  INLINE
  bool
  operator== (int x) const
  {
    return value == x;
  }

  INLINE
  bool
  operator< (int x) const
  {
    return value < x;
  }
};

static const unsigned int NODES_LOG = 9;

static container_t nodes[1 << NODES_LOG];
static container_t *remove_nodes[SIZE (nodes)];

static
unsigned int
overflows_cnt (full_stack_t &stack UNUSED)
{
  return 0;
}

template <typename STACK>
static
unsigned int
overflows_cnt (STACK &stack)
{
  return stack.overflows ();
};

template <unsigned int SZ>
struct stack_t
{
private:
  void *array[SZ];
  u64_t size;
  u64_t _mark;
  unsigned int _overflows;

public:
  stack_t ()
  {
    size = 0;
    _mark = 0;
    _overflows = 0;
  }

public:
  INLINE
  bool
  push (void *x)
  {
    if (size == SIZE (array))
      return false;

    array[size++] = x;
    return true;
  }

  INLINE
  void *
  pop ()
  {
    return array[--size];
  }

  INLINE
  void *
  top () const
  {
    return array[size - 1];
  }

  INLINE
  void
  mark ()
  {
    _mark = size;
  }

  INLINE
  void *
  replace_mark (void *x)
  {
    if (_mark == SIZE (array))
      return NULL;

    void *old = array[_mark];
    array[_mark] = x;
    return old;
  }

  INLINE
  void
  stats (u64_t overflows)
  {
    _overflows = (unsigned int) overflows;
  }

  INLINE
  unsigned int
  overflows ()
  {
    unsigned int result = _overflows;
    _overflows = 0;
    return result;
  }
};

template <typename TREE, typename STACK>
static bool
test (const char *prefix, bool test_lookup_p = false)
{
  TREE tree;
  STACK stack;
  unsigned int insert_overflows = 0;
  unsigned int remove_overflows = 0;
  unsigned int total_insert_overflows = 0;
  unsigned int total_remove_overflows = 0;
  unsigned int max_insert_overflows = 0;
  unsigned int max_remove_overflows = 0;

  for (unsigned int i = 0; i < SIZE (nodes); ++i)
    {
      if (!tree.insert (&nodes[i], stack))
        {
          printf ("%s: insert #%u failure.\n", prefix, i);
          return false;
        }

      unsigned int overflows = overflows_cnt (stack);
      total_insert_overflows += overflows;

      if (overflows > 0)
        insert_overflows++;

      if (overflows > max_insert_overflows)
        max_insert_overflows = overflows;

      nodes[i].in_tree_p = true;

      for (unsigned int j = 0; j < SIZE (nodes); ++j)
        if (nodes[j].in_tree_p)
          {
            if (!tree.__test_unit__contains_p (&nodes[j]))
              {
                printf ("%s: (insert #%u) does not contain #%u.\n",
                        prefix, i, j);
                return false;
              }
          }
        else
          {
            if (tree.__test_unit__contains_p (&nodes[j]))
              {
                printf ("%s: (insert #%u) contiains #%u.\n", prefix, i, j);
                return false;
              }
          }
    }

  container_t *min = tree.get_min ();
  container_t *max = tree.get_max ();
  int value = -1;

  if (min->value != 0)
    {
      printf ("%s: invalid first element.\n", prefix);
      return false;
    }

  if (max->value != SIZE (nodes) - 1)
    {
      printf ("%s: invalid last element.\n", prefix);
      return false;
    }

  for (container_t *x = min; x; value = x->value, x = tree.get_next (x))
    {
      if (x->value != value + 1)
        {
          printf ("%s: invalid forward order\n", prefix);
          return false;
        }
    }

  if (value != SIZE (nodes) - 1)
    {
      printf ("%s: premature end of forward order\n", prefix);
      return false;
    }

  value += 1;

  for (container_t *x = max; x; value = x->value, x = tree.get_prev (x))
    {
      if (x->value != value - 1)
        {
          printf ("%s: invalid backward order\n", prefix);
          return false;
        }
    }

  if (value != 0)
    {
      printf ("%s: premature end of backward order %i\n", prefix, value);
      return false;
    }

  for (unsigned int i = 0; i < SIZE (remove_nodes); ++i)
    {
      if (!tree.remove (remove_nodes[i], stack))
        {
          printf ("%s: remove #%u failure.\n", prefix, i);
          return false;
        }

      unsigned int overflows = overflows_cnt (stack);
      total_remove_overflows += overflows;

      if (overflows > 0)
        remove_overflows++;

      if (overflows > max_remove_overflows)
        max_remove_overflows = overflows;

      remove_nodes[i]->in_tree_p = false;

      for (unsigned int j = 0; j < SIZE (nodes); ++j)
        if (nodes[j].in_tree_p)
          {
            if (!tree.__test_unit__contains_p (&nodes[j]))
              {
                printf ("%s: (remove #%u) does not contiain #%u.\n",
                        prefix, i, j);
                return false;
              }
          }
        else
          {
            if (tree.__test_unit__contains_p (&nodes[j]))
              {
                printf ("%s: (remove #%u) contiains #%u.\n", prefix, i, j);
                return false;
              }
          }
    }

  int min_value = SIZE (nodes);
  int max_value = -1;

  for (unsigned int i = 0; i < SIZE (nodes); i += 2)
    {
      tree.insert (&nodes[i], stack);
      nodes[i].in_tree_p = true;
      if (nodes[i].value < min_value)
        min_value = nodes[i].value;
      if (nodes[i].value > max_value)
        max_value = nodes[i].value;
    }

  for (unsigned int i = 1; i < SIZE (nodes); i += 2)
    {
      tree.replace (&nodes[i - 1], &nodes[i]);
      value = nodes[i - 1].value;
      nodes[i - 1].value = nodes[i].value;
      nodes[i - 1].in_tree_p = false;
      nodes[i].value = value;
      nodes[i].in_tree_p = true;
    }

  min = tree.get_min ();
  max = tree.get_max ();

  if (min->value != min_value)
    {
      printf ("%s: (after replacements) invalid first element.\n", prefix);
      return false;
    }

  if (max->value != max_value)
    {
      printf ("%s: (after replacements) invalid last element.\n", prefix);
      return false;
    }

  value = -1;

  for (container_t *x = min; x; value = x->value, x = tree.get_next (x))
    {
      if (x->value <= value)
        {
          printf ("%s: (after replacements) invalid forward order\n", prefix);
          return false;
        }
    }

  if (value != max_value)
    {
      printf ("%s: (after replacements) premature end of forward order\n",
              prefix);
      return false;
    }

  value = SIZE (nodes);

  for (container_t *x = max; x; value = x->value, x = tree.get_prev (x))
    {
      if (x->value >= value)
        {
          printf ("%s: (after replacements) invalid backward order\n", prefix);
          return false;
        }
    }

  if (value != min_value)
    {
      printf ("%s: (after replacements) premature end of backward order %i\n",
              prefix, value);
      return false;
    }

  for (unsigned int i = 1; i < SIZE (nodes); i += 2)
    {
      if (!tree.remove (&nodes[i], stack))
        {
          printf ("%s: (after replacements) remove #%u failure.\n", prefix, i);
          return false;
        }

      value = nodes[i - 1].value;
      nodes[i - 1].value = nodes[i].value;
      nodes[i].value = value;
      nodes[i].in_tree_p = false;
    }

  if (test_lookup_p)
    {
      for (unsigned int i = 0; i < SIZE (nodes); i += 2)
        {
          tree.insert (&nodes[i], stack);
          nodes[i].in_tree_p = true;
        }

      for (unsigned int i = 0; i < SIZE (nodes); ++i)
        {
          if (tree.lookup (remove_nodes[i], stack))
            {
              if (!remove_nodes[i]->in_tree_p)
                {
                  printf ("%s: lookup #%u failure.\n", prefix, i);
                  return false;
                }
            }
          else
            {
              if (remove_nodes[i]->in_tree_p)
                {
                  printf ("%s: lookup #%u failure.\n", prefix, i);
                  return false;
                }
            }

          remove_nodes[i]->in_tree_p = false;
        }
    }

  if (insert_overflows > 0 || remove_overflows > 0)
    printf ("%s: %u/%u OVERFLOW(S) "
            "(%u/%u @ insert (max %u) + %u/%u @ remove (max %u))\n",
            prefix, insert_overflows + remove_overflows,
            total_insert_overflows + total_remove_overflows,
            insert_overflows, total_insert_overflows, max_insert_overflows,
            remove_overflows, total_remove_overflows, max_remove_overflows);
  else
    printf ("%s: SUCCESS\n", prefix);

  return true;
}

template <typename TREE>
static bool
test (const char *prefix, bool test_lookup_p = false)
{
  return test<TREE, full_stack_t> (prefix, test_lookup_p);
}

static unsigned int
my_rand ()
{
  unsigned int i = ((u64_t) rand () * SIZE (nodes)) / (u64_t) RAND_MAX;
  return i == SIZE (nodes) ? i - 1 : i;
}

int
main ()
{
  srand ((unsigned int) time (NULL));

  for (unsigned int i = 0; i < SIZE (nodes); ++i)
    {
      nodes[i].value = i;
      remove_nodes[i] = &nodes[i];
    }

  for (unsigned int i = 0; i < SIZE (nodes) / 2; ++i)
    {
      unsigned int i1 = my_rand ();
      unsigned int i2 = my_rand ();
      unsigned int tmp = nodes[i1].value;
      nodes[i1].value = nodes[i2].value;
      nodes[i2].value = tmp;
    }

  for (unsigned int i = 0; i < SIZE (nodes) / 2; ++i)
    {
      unsigned int i1 = my_rand ();
      unsigned int i2 = my_rand ();
      container_t *tmp = remove_nodes[i1];
      remove_nodes[i1] = remove_nodes[i2];
      remove_nodes[i2] = tmp;
    }

  bool result =
    test<tree_t<node_t<container_t, basic_node_t>, basic_minmax_tree_t,
                minmax_glue_t> > ("BST+plain")
    && test<tree_t<parent_node_t<container_t, basic_parent_node_t>,
                   basic_minmax_tree_t, minmax_glue_t> > ("BST+parent")
    && test<tree_t<parent_next_node_t<container_t, basic_parent_next_node_t>,
                   basic_minmax_tree_t, minmax_glue_t> > ("BST+parent_next")
    && test<tree_t<parent_pn_node_t<container_t, basic_parent_pn_node_t>,
                   basic_minmax_tree_t, minmax_glue_t> > ("BST+parent_pn")
    && test<tree_t<thread_node_t<container_t, basic_thread_node_t>,
                   basic_minmax_tree_t, minmax_glue_t> > ("BST+thread")
    && test<avl_tree_t<node_t<container_t, basic_avl_node_t<basic_node_t> >,
                       basic_minmax_tree_t, minmax_glue_t> > ("AVL+plain")
    && test<avl_tree_t<node_t<container_t, basic_avl_node_t<basic_node_t> >,
                       basic_minmax_tree_t, minmax_glue_t>,
            stack_t<NODES_LOG + NODES_LOG / 2> >
         ("AVL+plain+stack")
    && test<avl_tree_t<node_t<container_t,
                              basic_avl_node_t<basic_parent_node_t> >,
                       basic_minmax_tree_t, minmax_glue_t> > ("AVL+parent")
    && test<avl_tree_t<node_t<container_t,
                              basic_avl_node_t<basic_thread_node_t> >,
                       basic_minmax_tree_t, minmax_glue_t> > ("AVL+thread")
    && test<rb_tree_t<node_t<container_t, basic_rb_node_t<basic_node_t> >,
                      basic_minmax_tree_t, minmax_glue_t> > ("RB+plain")
    && test<rb_tree_t<node_t<container_t, basic_rb_node_t<basic_node_t> >,
                      basic_minmax_tree_t, minmax_glue_t>,
            stack_t<NODES_LOG * 2> >
         ("RB+plain+stack")
    && test<rb_tree_t<node_t<container_t,
                             basic_rb_node_t<basic_parent_node_t> >,
                      basic_minmax_tree_t, minmax_glue_t> > ("RB+parent")
    && test<rb_tree_t<node_t<container_t,
                             basic_rb_node_t<basic_thread_node_t> >,
                      basic_minmax_tree_t, minmax_glue_t> > ("RB+thread")
    && test<splay_tree_t<node_t<container_t, basic_node_t>,
                         basic_minmax_tree_t, minmax_glue_t> >
         ("SPLAY+plain", true)
    && test<splay_tree_t<node_t<container_t, basic_node_t>,
                         basic_minmax_tree_t, minmax_glue_t>,
            stack_t<NODES_LOG * 3> >
         ("SPLAY+plain+stack", true)
    && test<splay_tree_t<parent_node_t<container_t, basic_parent_node_t>,
                         basic_minmax_tree_t, minmax_glue_t> >
         ("SPLAY+parent", true)
    && test<splay_tree_t<thread_node_t<container_t, basic_thread_node_t>,
                         basic_minmax_tree_t, minmax_glue_t> >
         ("SPLAY+thread", true);

  return result ? 0 : 1;
}

